$remaining_vertices = []
$visited_vertices = {}

def get_random_vertex()
   v = $remaining_vertices.sample
  while $visited_vertices[v]
    v = $remaining_vertices.sample
  end
  $visited_vertices[v] = true

  return v
end


def greedy(vertices, s)
  #puts "greedy algo"

  return s if vertices.empty?

  max = -1
  v_max_index = -1

  i=0
  vertices.each { |v|
    num_adjoinable_vertices = vertices.size - (vertices & v.adjList).size - 1

    #puts "v = #{v}, rho= #{num_adjoinable_vertices}"

    if num_adjoinable_vertices > max
      max = num_adjoinable_vertices
      v_max_index = i
    end

    i+=1
  }

  #puts "v_max= #{vertices[v_max_index]}, rho= #{max}"
  #puts ""

  v = vertices[v_max_index]
  s << v
  vertices.delete_at(v_max_index)
  v.adjList.each { |w|
    vertices.delete(w)
  }

  #puts "s #{s}"
  #puts "vertices #{vertices}"

  return greedy(vertices, s)

end


def compute_sufficient_size_for_maximum_independent_set(g)
  #a mathematical formula states that the number of independent actors is at least k
  #where k = n/(m+1), rounded up to the nearest integer
  #m is the maximum vertex degree in the graph, (i.e. the max number of neighbours)

  n = g.count_v

  max_degree = 0
  g.vertices.each { |v|

      #get degree of v (i.e. num of neighbours)
      degree = v.adjList.size
      max_degree = degree if degree > max_degree
  }

  #compute sufficient size for maximum independent set
  sufficient_size = ( n / (max_degree+1.0) ).ceil #ceil means ceiling (i.e. round up)

  #puts
  #puts "n=#{n}, max_degree=#{max_degree}, k=#{sufficient_size}"

  return sufficient_size
end

def delete_neighbours(vertices, v)
  v.adjList.each { |w|
    vertices.delete(w)
  }
end


def local_search(vertices, s)

  #s_vw = s.clone
  x = nil
  w = nil

  vertices.each { |v|
    w = v.adjList & s
    if w.size == 1
      x = w[0]
      s.delete(x)
      s << v

      break;
    end
  }

  vertices.delete(x)
  vertices |= w

  s.each { |y|
    delete_neighbours(vertices, y)
    vertices.delete(y)
  }
  return greedy(vertices, s)
end



# Q4 - this method will only be invoked AFTER Q3(a) and Q3(b) have been tested on the submission server
def run_algo(g)

  #$remaining_vertices = g.vertices.clone
  #n = $remaining_vertices.size

  time = Time.now

  k = compute_sufficient_size_for_maximum_independent_set(g)

  mis = []
  mis_selected = []

  g.vertices.each { |v|
    #v = get_random_vertex
    s = [v]

    #-- calling of greedy algo --
    vertices_copy = g.vertices.clone
    delete_neighbours(vertices_copy, v)
    vertices_copy.delete(v)
    #puts
    #puts "s= #{s}"
    #puts "vertices= #{vertices_copy}"
    s = greedy(vertices_copy, s)
    #if we  have a set size of at least k
    mis << s
    mis_selected << s if s.size >= k
    break if mis.size == 4
    #-- calling of greedy algo end --
  }


  ans = []
  mis = mis_selected if mis_selected == 3

  #PART 2
  n = mis.size
  for i in 0..n-1
    s_i = mis[i]

    for j in 0..n-1
      s_j = mis[j]
      next if s_i == s_j

      s = s_i & s_j

      #-- calling of procedure 1 --
      vertices1 = g.vertices.clone
      s.each { |v|
        delete_neighbours(vertices1, v)
        vertices1.delete(v)
      }
      s = greedy(vertices1, s)
      #base case
      if s.size >= k
        ans << s
        next
      end
      #-- calling of procedure 1 end --

      #-- calling of procedure 2 --
      k.times {
        vertices2 = g.vertices.clone
        s.each { |w|
          vertices2.delete(w)
        }
        s = local_search(vertices2, s)
      }
      #base case
      if s.size >= k
        #maximal_independent_sets << s
        ans << s
        next
      end
      #-- calling of procedure 2 end --

    end

  end


  b = []
  ans.each { |a|
    b = a if a.size > b.size
  }


  puts "Execution: #{Time.now - time} s"
  puts "Quality: #{b.size}"

  return b

end
#-------------------------------------------------------------------
